#![allow(dead_code)]

use core::iter::Iterator;

// ************************************************
// Minimal jumpping times
// given list return minimal jumpping times
// ************************************************
pub fn jump() -> i32 {
    // let nums = vec![2, 3, 1, 1, 4];
    let nums = vec![1, 2, 3, 4];

    // using establish bridge idea
    // find the max rightest point one by one
    // if get the cur shift the end point.
    let mut ans = 0;
    let mut cur_right_index = 0;
    let mut next_right = 0;

    for i in 0..nums.len() {
        next_right = next_right.max(i + nums[i]);
        if i == cur_right_index {
            cur_right_index = next_right;
            ans += 1;
        }
    }
    ans
}

// ************************************************
// candy problem
// find the minimal candy amount ensure at least 1 for single
// each higher rate one have more than left and right
// ************************************************
pub fn candy() -> i32 {
    let ratings = vec![2, 4, 0, 3, 1];
    //                 3, 5, 1, 4, 2
    //                 1, 2, 1, 2, 1
    // 4, 0, 4, 8, 2, 1
    // 2, 1, 2, 3, 2, 1
    // 1, 0, 2
    // 1, 1, 2
    // 2, 1, 2

    // get min rate, set it to 1
    let mut candies = vec![1; ratings.len()];

    // left to right,
    for i in 1..ratings.len() {
        if ratings[i] > ratings[i - 1] {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // right to left
    for i in (0..ratings.len() - 1).rev() {
        if ratings[i] > ratings[i + 1] {
            candies[i] = candies[i].max(candies[i + 1] + 1);
        }
    }

    candies.iter().sum()
    // return sum of candies
}

// ************************************************
// save water problem
// find the waters it can save
// ************************************************
pub fn trap() -> i32 {
    let height = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

    // let mut waters = vec![0; height.len()];
    // waters[0] = height[0];

    // // from left to right
    // for i in 1..height.len() {
    //     waters[i] = waters[i - 1].max(height[i]);
    // }

    // let mut ans = 0;
    // let mut right_max = height[height.len() - 1];

    // // from right to left
    // for i in (0..height.len()).rev() {
    //     right_max = right_max.max(height[i]);
    //     ans += right_max.min(waters[i]) - height[i];
    // }

    // println!("{}", ans);

    // // return waters sum
    // ans

    // Solution with singluar stack, simpler.
    let mut stack = Vec::new();
    let mut ans = 0;

    for i in 0..height.len() {
        while let Some(&top) = stack.last() {
            // if comes a higher pillar
            if height[i] <= height[top] {
                // smaller, break to push
                break;
            }
            // pop one
            stack.pop();

            if let Some(&left) = stack.last() {
                let width = i - left - 1;
                let h = height[i].min(height[left]) - height[top];
                ans += (width as i32) * h;
            }
        }
        stack.push(i);
    }

    ans
}
